<HTML><HEAD><TITLE>library(tentative)</TITLE></HEAD><BODY>
[ <A HREF="../../index.html">Reference Manual</A> | <A HREF="../../fullindex.html">Alphabetic Index</A> ]<H1>library(tentative)</H1>
A framework for Local Search based on tentative values
<H2>Predicates</H2>
<BLOCKQUOTE>
<DL>
<DT><A HREF="NT-2.html"><STRONG>CS :~ ConstrSpec</STRONG></A></DT>
<DD>Add a constraint to a constraint set</DD>
<DT><A HREF="cs_all-2.html"><STRONG>cs_all(+CS, -Cstr)</STRONG></A></DT>
<DD>Get all constraints in the constraint set</DD>
<DT><A HREF="cs_all_violated-2.html"><STRONG>cs_all_violated(+CS, -Cstr)</STRONG></A></DT>
<DD>Get all violated constraints in the constraint set</DD>
<DT><A HREF="cs_all_worst-2.html"><STRONG>cs_all_worst(+CS, -Cstr)</STRONG></A></DT>
<DD>Get all worst violated constraints in the constraint set</DD>
<DT><A HREF="cs_clear_all-1.html"><STRONG>cs_clear_all(+CS)</STRONG></A></DT>
<DD>Clean up the constraint set completely</DD>
<DT><A HREF="cs_clear_satisfied-1.html"><STRONG>cs_clear_satisfied(+CS)</STRONG></A></DT>
<DD>Remove the satisfied constraints from the constraint set</DD>
<DT><A HREF="cs_create-2.html"><STRONG>cs_create(-CS, ++Options)</STRONG></A></DT>
<DD>Create an empty constraint set</DD>
<DT><A HREF="cs_current_violations-2.html"><STRONG>cs_current_violations(+CS, -Vio)</STRONG></A></DT>
<DD>Get the current violatedness of the constraint set</DD>
<DT><A HREF="cs_random_violated-2.html"><STRONG>cs_random_violated(+CS, -Cstr)</STRONG></A></DT>
<DD>Get random violated constraints in the constraint set</DD>
<DT><A HREF="cs_random_worst-2.html"><STRONG>cs_random_worst(+CS, -Cstr)</STRONG></A></DT>
<DD>Get random worst violated constraint from the constraint set</DD>
<DT><A HREF="cs_violations-2.html"><STRONG>cs_violations(+CS, -Vio)</STRONG></A></DT>
<DD>Get a tentative variable reflecting the violatedness of the constraint set</DD>
<DT><STRONG>get_changeable_value(?, ?)</STRONG></DT>
<DD>No description available</DD>
<DT><A HREF="has_tent_value-1.html"><STRONG>has_tent_value(?X)</STRONG></A></DT>
<DD>X has a tentative value (succeeds also for X nonvar)</DD>
<DT><STRONG>print_tentative(?, ?)</STRONG></DT>
<DD>No description available</DD>
<DT><A HREF="random_element-2.html"><STRONG>random_element(+Values, -X)</STRONG></A></DT>
<DD>Pick random element from range or collection</DD>
<DT><A HREF="random_sample-3.html"><STRONG>random_sample(+Values, +SampleSize, -X)</STRONG></A></DT>
<DD>Nondeterministically pick SampleSize random elements</DD>
<DT><A HREF="register_for_notification-3.html"><STRONG>register_for_notification(?X, +Tag, ?Receiver)</STRONG></A></DT>
<DD>Constraint implementation: register for notification</DD>
<DT><STRONG>suspend_on_change(?, ?)</STRONG></DT>
<DD>No description available</DD>
<DT><A HREF="tent_fix-1.html"><STRONG>tent_fix(?X)</STRONG></A></DT>
<DD>Instantiate X to its tentative value</DD>
<DT><A HREF="tent_get-2.html"><STRONG>tent_get(?X, -TV)</STRONG></A></DT>
<DD>Get X's tentative value</DD>
<DT><A HREF="tent_implements-2.html"><STRONG>++ImplSpec tent_implements ++ConsSpec</STRONG></A></DT>
<DD>Associate a constraint with a tentative value implementation</DD>
<DT><A HREF="tent_is-2.html"><STRONG>?Result tent_is +Expr</STRONG></A></DT>
<DD>Maintain tentative result of arithmetic expression</DD>
<DT><A HREF="tent_minimize_random-3.html"><STRONG>tent_minimize_random(+MoveGenerator, ?Violations, -MoveId)</STRONG></A></DT>
<DD>Find a move that minimizes violations</DD>
<DT><A HREF="tent_set-2.html"><STRONG>tent_set(?X, +TV)</STRONG></A></DT>
<DD>Set X's tentative value to TV</DD>
<DT><A HREF="tent_set_all-2.html"><STRONG>tent_set_all(?Vars, +TV)</STRONG></A></DT>
<DD>Set the tentative values of all variables within Vars to the same value TV</DD>
<DT><STRONG>tent_set_attr(?, ?)</STRONG></DT>
<DD>No description available</DD>
<DT><A HREF="tent_set_random-2.html"><STRONG>tent_set_random(?Vars, ++Values)</STRONG></A></DT>
<DD>Set the tentative value of each variable within Vars to a random value from the given Range</DD>
<DT><A HREF="tent_trace_array-3.html"><STRONG>tent_trace_array(+Stream, +Name, +ArrayList)</STRONG></A></DT>
<DD>Simple tracing facility for several variables</DD>
<DT><A HREF="var_get_violations-2.html"><STRONG>var_get_violations(?X, -Violations)</STRONG></A></DT>
<DD>Get X's violation count</DD>
<DT><A HREF="var_inc_violations-2.html"><STRONG>var_inc_violations(?X, +Delta)</STRONG></A></DT>
<DD>Increment X's violation count by Delta</DD>
<DT><A HREF="vs_all-2.html"><STRONG>vs_all(+VS, -Vars)</STRONG></A></DT>
<DD>Retrieve all variables from a varset</DD>
<DT><A HREF="vs_all_violated-2.html"><STRONG>vs_all_violated(+VS, -Vars)</STRONG></A></DT>
<DD>Retrieve all violated variables from a varset</DD>
<DT><A HREF="vs_all_violated_index-2.html"><STRONG>vs_all_violated_index(+VS, -Vars)</STRONG></A></DT>
<DD>Retrieve all violated variable indices from a varset</DD>
<DT><A HREF="vs_all_worst-2.html"><STRONG>vs_all_worst(+VS, -Vars)</STRONG></A></DT>
<DD>Retrieve all worst violated variables from a varset</DD>
<DT><A HREF="vs_all_worst_index-2.html"><STRONG>vs_all_worst_index(+VS, -Vars)</STRONG></A></DT>
<DD>Retrieve all worst violated variable indices from a varset</DD>
<DT><A HREF="vs_create-2.html"><STRONG>vs_create(?Vars, -VS)</STRONG></A></DT>
<DD>Construct a varset from the variables in Vars</DD>
<DT><A HREF="vs_element-3.html"><STRONG>vs_element(+VS, +I, -X)</STRONG></A></DT>
<DD>Get an element of a varset by index</DD>
<DT><A HREF="vs_member-2.html"><STRONG>vs_member(+VS, -X)</STRONG></A></DT>
<DD>Succeed for each element of a varset</DD>
<DT><A HREF="vs_random-2.html"><STRONG>vs_random(+VS, -Var)</STRONG></A></DT>
<DD>Retrieve a random variable from a varset</DD>
<DT><A HREF="vs_random_index-2.html"><STRONG>vs_random_index(+VS, -Var)</STRONG></A></DT>
<DD>Retrieve a random variable index from a varset</DD>
<DT><A HREF="vs_random_violated-2.html"><STRONG>vs_random_violated(+VS, -Var)</STRONG></A></DT>
<DD>Retrieve a random violated variable from a varset</DD>
<DT><A HREF="vs_random_violated_index-2.html"><STRONG>vs_random_violated_index(+VS, -I)</STRONG></A></DT>
<DD>Retrieve a random violated variable index from a varset</DD>
<DT><A HREF="vs_random_worst-2.html"><STRONG>vs_random_worst(+VS, -Var)</STRONG></A></DT>
<DD>Retrieve a worst violated variable from a varset</DD>
<DT><A HREF="vs_random_worst_index-2.html"><STRONG>vs_random_worst_index(+VS, -Var)</STRONG></A></DT>
<DD>Retrieve a worst violated variable index from a varset</DD>
<DT><A HREF="vs_size-2.html"><STRONG>vs_size(+VS, -N)</STRONG></A></DT>
<DD>Get the size of a varset</DD>
<DT><A HREF="vs_violated-2.html"><STRONG>vs_violated(+VS, -Vars)</STRONG></A></DT>
<DD>Succeeds for each violated variable from a varset</DD>
<DT><A HREF="vs_violated_index-2.html"><STRONG>vs_violated_index(+VS, -Vars)</STRONG></A></DT>
<DD>Succeeds for each violated variable index from a varset</DD>
<DT><A HREF="vs_worst-2.html"><STRONG>vs_worst(+VS, -Vars)</STRONG></A></DT>
<DD>Succeeds for each worst violated variable from a varset</DD>
<DT><A HREF="vs_worst_index-2.html"><STRONG>vs_worst_index(+VS, -Vars)</STRONG></A></DT>
<DD>Succeeds for each worst violated variable index from a varset</DD>
</DL>
</BLOCKQUOTE>
<H2>Structures</H2>
<BLOCKQUOTE>
<DL>
<DT><STRONG>struct monitored_constraint(alias, violations, suspensions)</STRONG></DT>
<DD>No description available</DD>
</DL>
</BLOCKQUOTE>
<H2>Other Exports</H2>
<BLOCKQUOTE><DL>
<DT><STRONG>export op(700, xfx, tent_get)</STRONG></DT><DD></DD>
<DT><STRONG>export op(700, xfx, tent_set)</STRONG></DT><DD></DD>
<DT><STRONG>export op(700, xfx, tent_implements)</STRONG></DT><DD></DD>
<DT><STRONG>export op(800, xfx, alias)</STRONG></DT><DD></DD>
<DT><STRONG>export op(900, xfx, :~)</STRONG></DT><DD></DD>
<DT><STRONG>export op(700, xfx, tent_is)</STRONG></DT><DD></DD>
</DL></BLOCKQUOTE>
<H2>Description</H2>

    <h3>Overview</h3>
<P>
    This is a library for implementing Local Search algorithms.
    It is intended as a successor for library(repair).
</P><P>
    This library provides the following concepts and primitives:
<UL><LI>
    A variable can be given a <EM>tentative value</EM>. This is a value which
    is attached to the variable, but does not constrain the variable.
</LI><LI>
    Tentative values are observed by <EM>monitored constraints</EM>. A monitored
    constraint checks whether a constraint is satisfied given the current
    tentative values of its variables, or computes a measure of violatedness
    for a tentatively violated constraint.
</LI><LI>
    <EM>Violatedness</EM> can be attached to constraints and to variables.
    Typically, when a constraint is tentatively violated, this increases
    the violatedness count of the constraint itself, and the violatedness
    count of those variables that can be made responsible for the violation.
</LI></UL>
    Actual constraint implementations can be found in the library
    <EM>lib(tentative_constraints)</EM>.
</P>

    <h3>Tentative Values</h3>
<P>
    A tentative value (TV) can be an atomic term or a (possibly nonground)
    compound term. It is a conscious design choice not to allow variable
    tentative values.
    A tentative value can be attached to a variable, and freely changed.
    It is not possible to remove a variable's tentative value once
    it has had one, it can only be replaced by a different one.
    The change of tentative value can be used as a trigger condition for
    waking delayed goals.
</P><P>
    Instantiating a tentative variable to a value V is equivalent to first
    setting/changing its tentative value to V, and then instantiating to V.
    Unifying two tentative variables is not supported and raises an error.
</P><P>
    Variables with tentative value are printed in the following format:
<PRE>
	X{99 -> 7}
</PRE>
    where the first number (99) is the tentative value, and the second
    number (7) is the variable's violation count.
</P><P>
    The primitives related to tentative values are:
<blockquote><dl>
    <dt>has_tent_value(?X)</dt>
	<dd>X has a tentative (of definitive) value</dd>
    <dt>tent_get(?X, -Val)</dt>
	<dd>get tentative values</dd>
    <dt>tent_set(?X, -Val)</dt>
	<dd>set tentative values</dd>
    <dt>tent_set_all(?Xs, +Val)</dt>
	<dd>set multiple identical tentative values</dd>
    <dt>tent_set_random(?Xs, +Range)</dt>
	<dd>set multiple random tentative values</dd>
    <dt>tent_fix(?X)</dt>
	<dd>instantiate to tentative value</dd>
    <dt>var_get_violations(?X, -Violations)</dt>
	<dd>get the number of violations the variable is currently involved in</dd>
    <dt>var_inc_violations(?Var, +Delta)</dt>
	<dd>add Delta to Var's violation counter</dd>
</dl></blockquote>
    All these operations are undone on backtracking.
</P>


    <h3>Variable Sets</h3>
<P>
    Tentative variables can be grouped into indexed sets, from which elements
    (or their index) can then be selected according to different criteria.
    The corresponding predicates are:
<blockquote><dl>
    <dt>vs_create(+Vars, -VarSet)</dt>
        <dd>construct a variable set from the variables in Vars</dd>
    <dt>vs_all(+VS, -Vs)</dt>
        <dd>get a list of all the variables in the set</dd>
    <dt>vs_element(+VS, +I, -V)</dt>
        <dd>get a particular variable from the set</dd>
    <dt>vs_member(+VS, -V)</dt>
        <dd>enumerate all variables from the set</dd>
    <dt>vs_random(+VS, -Vs), vs_random_index(+VS, -Is)</dt>
        <dd>pick a random variable from the set</dd>
    <dt>vs_random_violated(+VS, -Vs), vs_random_violated_index(+VS, -Is)</dt>
        <dd>pick a random violated variable from the set</dd>
    <dt>vs_all_violated(+VS, -Vs), vs_all_violated_index(+VS, -Is)</dt>
        <dd>get a list of all violated variables from the set</dd>
    <dt>vs_violated(+VS, -V), vs_violated_index(+VS, -I)</dt>
        <dd>enumerate all violated variables from the set</dd>
    <dt>vs_random_worst(+VarSet, -WorstVar), vs_random_worst_index(+VarSet, -I)</dt>
    	<dd>pick a random variable with maximum violations from the set</dd>
    <dt>vs_all_worst(+VS, -Vs), vs_all_worst_index(+VS, -Is)</dt>
        <dd>get a list of all the maximally violated variables from the set</dd>
    <dt>vs_worst(+VS, -V), vs_worst_index(+VS, -I)</dt>
        <dd>enumerate all maximally violated variables from the set</dd>
</dl></blockquote>
</P>


    <h3>Constraint Sets</h3>
<P>
    To monitor a constraint's tentative violatedness, it must be added
    to a constraint set.  The predicates to create, add and remove
    constraints from a constraint set are:
<blockquote><dl>
    <dt>CS :~ C</dt>
    	<dd>add a constraint to the constraint set</dd>
    <dt>cs_create(-CS, +Options)</dt>
    	<dd>create an empty constraint set</dd>
    <dt>cs_clear_all(+CS)</dt>
    	<dd>remove all constraints from the constraint set</dd>
    <dt>cs_clear_satisfied(+CS)</dt>
    	<dd>remove all satisfied constraints from the constraint set</dd>
</dl></blockquote>
    The total violation count of all the constraints in the set can be
    accessed through the following predicates:
<blockquote><dl>
    <dt>cs_violations(+CS, -VioVar)</dt>
    	<dd>get a tentative variable reflecting violatedness of the constraint set</dd>
    <dt>cs_current_violations(+CS, -Vio)</dt>
    	<dd>get the current violatedness of the constraint set (integer)</dd>
</dl></blockquote>
    Constraints from the constraint set can be selected according to
    different criteria through the following predicates:
<blockquote><dl>
    <dt>cs_random_worst(+CS, -C)</dt>
    	<dd>get a random worst violated constraint from the constraint set</dd>
    <dt>cs_all_worst(+CS, -Cs)</dt>
    	<dd>get all worst violated constraints from the constraint set</dd>
    <dt>cs_all_violated(+CS, -Cs)</dt>
    	<dd>get all violated constraints from the constraint set</dd>
    <dt>cs_random_violated(+CS, -Cs)</dt>
    	<dd>get a random violated constraint from the constraint set</dd>
    <dt>cs_all(+CS, -Cs)</dt>
    	<dd>get all constraints from the constraint set</dd>
</dl></blockquote>
</P>


    <h3>Invariants</h3>
<P>
    There is currently one primitive to maintain arithmetic invariants:
<blockquote><dl>
    <dt>-Res tent_is +Expr</dt>
    	<dd>the tentative value of Res is the tentative result of Expr</dd>
</dl></blockquote>
</P>


    <h3>Search and Randomised Primitives</h3>
<P>
    The following primitives support the implementation of the actual
    Local Search routines:
<blockquote><dl>
    <dt>tent_minimize_random(MoveGenerator, Violations, MoveId)</dt>
    	<dd>Find a best neighbour using MoveGenerator</dd>

    <dt>random_element(+Range, -Value)</dt>
	<dd>Pick a random element from Range</dd>

    <dt>random_sample(+Range, +N, -Value)</dt>
    	<dd>Succeed N times with random values from Range</dd>
</dl></blockquote>
</P>


    <h3>Tracing</h3>
<P>
    A simple tracing facility is provided via
<blockquote><dl>
    <dt>tent_trace_array(+Stream, +Name, +ArrayList)</dt>
    	<dd>Print a message whenever a tentative value changes</dd>
</dl></blockquote>

    Also, the Visualisation Tools can be used with this library,
    by creating viewables with type changeable(tentative,Type).
</P>


    <h3>Constraint implementation interface</h3>
<P>
    Constraints are implemented by an implementation predicate. A constraint
    is linked to its implementation predicate by a tent_implements/2
    declaration, e.g.
<pre>
	:- alldifferent_t/2 tent_implements alldifferent/1.
</pre>
    The implementation predicate must have one more argument than the
    constraint itself.  The extra (last) argument is a structure
<pre>
	struct(monitored_constraint(
		alias,		% the constraint goal (or equivalent term)
		violations,	% a tentative variable
		suspensions	% suspensions of the monitoring goals
	)
</pre>
    The implementation predicate is supposed to update the constraint's
    violation TV plus the violation counters of the variables that occur
    in the constraint. It should do this by suspending on the variable's
    tent_chg list, and by registering for exact change notification via:
<blockquote><dl>
    <dt>register_for_notification(?TV, +Tag, ?Receiver)</dt>
    	<dd>register to receive messages about changes to TV's tentative value</dd>
</dl></blockquote>
     This messaging facility is based upon the primitive in lib(notify_ports).
</P>


    <h3>Constraints</h3>
<P>
    Actual constraint implementations can be found in the library
    <EM>lib(tentative_constraints)</EM>.
</P>


    <h3>Example</h3>
<P>
    See <EM>lib(tentative_constraints)</EM>.
</P>

<H2>About</H2><UL COMPACT>
<LI><STRONG>Author: </STRONG>Joachim Schimpf
<LI><STRONG>Copyright &copy; </STRONG>Cisco Systems
<LI><STRONG>Date: </STRONG>$Date: 2009/02/19 05:45:20 $
</UL>
<H2>See Also</H2>
<A HREF="../../lib/tentative_constraints/index.html">library(tentative_constraints)</A><HR>Generated from tentative.eci on 2009-05-27 01:25
</BODY></HTML>
